The present invention relates to high level synthesis for datapaths methods for providing Built-In-Self-Repair (BISR) of circuits. Specifically, the BISR synthesis methods eliminate the limitation in the previously employed method of replacing a failed module of one type with a replacement module of the same type. In accordance with the teachings of the present invention, replacement of modules of different types with the same spare units is achieved by using the design space exploration abilities of high level synthesis. One method involves resource allocation, assignment and scheduling. Another method involves transformation (retiming, associativity and the inverse element law).
As the complexity of chip designs increases, fault tolerance techniques such as BISR play an increasingly important role in reliability and yield improvement. BISR is a hybrid redundancy technique where in addition to N core operational modules, a set of spare modules is provided. If a faulty core module is detected, it is replaced with a spare module.
As the cost of semiconductor manufacturing increases, it becomes imperative to improve process yields as fast as possible. Process improvement techniques such as BISR therefore become very important. BISR sparing methodology is a conceptually simple, yet powerful technique for increasing yield by adding redundant modules to the design. If a chip is found to have defective modules, these modules can be replaced by good modules before packaging. Similarly, these same BISR methods can also be applied to improve chip reliability. Chips can be made more fault tolerant to failures that occur during operation, by automatic replacement of failed modules with spare ones, so that the overall system can continue to function correctly. This is especially important in military systems and space exploration missions where it is critical that there arc no system failures, even in the face of errors, or where manual replacement of failed modules is either impossible or prohibitively expensive.
BISR techniques arc regularly used during the development and operation of primary and secondary memories and sometimes in general purpose bit-sliced execution units. They have not received appropriate attention in ASIC design, but the ever increasing level of integration should make them an important methodology for ASIC yield improvement.
The present invention concerns a novel method of BISR primarily intended for ASIC designs, which can be used for yield improvement or fault-tolerance against permanent faults. The method is broadly based upon the flexibility provided by high level synthesis during design space exploration. The identification and the techniques for exploiting this flexibility are also important aspects of the invention. Intelligent strategies to use the flexibility of solutions is the crucial component for achieving minimum overhead designs of a reconfigurable datapath which can be used not only for a BISR design, but also for design of an Application Specific Programmable Processor (ASPP). Minimum hardware overhead is achieved most often by identifying a set of configurations which are similar in terms of the required hardware resources. Consider, for example, the design of an ASPP to implement the 2 different computations A and B. Let Ai and Bj represent particular implementation solutions for the computations A and B, where (i) and (j) are the total number of possible implementations of A and B respectively. As the ASPP implementation must be able to implement both computations, its hardware is the ration of the hardware, Ai.orgate.Bj, for any i and j. The goal is not to find the Min(Ai).orgate.Min(Bj)implementations, but to find the Min(Ai.orgate.Bj) solution, which in many instances is one for which Ai and Bj have similar hardware implementations. The methods described below have a high potential to facilitate the synthesis of ASPP datapaths due to their ability to produce a great variety of alternative solutions. This increases the likelihood of finding the solution pair (Ai, Bj), for which both Ai and Bj have a small implementation cost and require mainly identical resources.
High level synthesis provides the flexibility of design space exploration so that a variety of design goals can be addressed. Little work has been done on high level synthesis techniques for fault tolerant design. Raghavendra and Lursinsap in an article entitled "Automated Micro-Roll-Back Self Recovery Synthesis" in the 28th ACM/IEEE Design Automation Conference, pp 385 to 390, 1991, concentrated on designs with self-recovery from transient faults using micro roll-back and checkpoint insertion. Karri and Orailoglu in an article entitled "Transformation-Based High-Level Synthesis of Fault-Tolerant ASIC," in the 29th ACM/IEEE Design Automation conference, pp. 662 to 665, 1992 presented a transformation based method for minimizing hardware overhead while achieving a certain level of fault tolerance for common mode failures. Previous high level synthesis methods for enhancing fault tolerance have addressed intermittent and transient faults. See, for instance, D. P. Siewiorek and R. S. Swartz book entitled "Reliable Computer Systems: Design and Evaluation", 2nd ed, Digital Press, Burlington, Mass., 1992. The present invention concentrates on permanent faults, where fault tolerance is used for yield enhancement.
The main object for BISR techniques are systems that are bit-, byte-, or digit- sliced. These systems includes SRAM and DRAM memories, which are made from a set of bit planes and arithmetic-logic units (ALUs), assembled from ALU byte slices. By far the most important use of bit-sliced BISR is in SRAM and DRAM circuits, which is regularly used in almost all present day memory designs. The bit-sliced BISR in memories significantly increases memory production profitability. A simple, yet powerful methodology or implementation of ALU byte slices was proposed by Levitt et al. in "A Study of the Data Communication Problems in a Self-Repairable Multiprocessor, Conf. Proc. of AFIPS, v 32, pp 515-527, Thompson Book, Washington, DC 1968. Another important technique for preserving data through a failure occurrence in primary storage systems was proposed by Arulpragasm and Swartz in "A Design for Process State Preservation on Storage Unit Failure", 10th Int'l Syrup. on Fault-Tolerant Computing, pp 47-52, 1980. The concept is based on the use of a shadow box, a spare memory box which is identical to the other M operating memory boxes. A word stored at address j is the XOR of the words stored at location j in the other M operating boxes and has to be updated after each write to the memory system. In this reliability scheme, the content of a lost box can be reconstructed from the operating boxes and the shadow box by XORing values at corresponding locations. The shadow box technique has been recently extended to secondary memory storage. It is conceptually similar to the Arulpragasm and Swartz technique but makes updates on either a word or page basis.
Massive parallelism is another area where BISR is starting to play a crucial role, which will become increasingly prominent with greater use of concurrent computations. For example, a recently designed 11-Million Transistor neural network execution engine, has a triple-level redundancy structure resulting in the consumption of an additional 2.8 million transistors for BISR. In wafer scale integration, BISR also plays a prominent role. In a highly integrated ULSI system which contains both DRAM and SRAM as well as uncommitted gate- array, statistical studies showed that the BISR technique called interchip relief significantly improves the yield. The role of BISR techniques in systolic arrays designs has been described in the literature, though mostly from a theoretical and statistical point of view. Finally, in space exploration applications, redundancy through standby sparing is used extensively.
BISR methodology is not limited to memory and execution units. For example it has been proposed in the use of a backup fault tolerant clock.